{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0",
   "metadata": {},
   "source": [
    "# Genetic Programming using EvoTorch\n",
    "\n",
    "In this example, we perform genetic programming where the fitness function is a stack-based expression interpreter. While this notebook does not represent the state-of-the-art in the field of genetic programming, it can be a useful example as it demonstrates the following:\n",
    "\n",
    "- How to use the vectorized data structures provided by EvoTorch\n",
    "- How to use `GeneticAlgorithm` to solve discrete optimization problems\n",
    "- How to define problem-specific mutation operators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1",
   "metadata": {},
   "outputs": [],
   "source": [
    "from evotorch import Problem, SolutionBatch\n",
    "from evotorch.operators import TwoPointCrossOver\n",
    "from evotorch.algorithms import GeneticAlgorithm\n",
    "from evotorch.logging import StdOutLogger\n",
    "from evotorch.tools.structures import CList\n",
    "from typing import Callable, Iterable, Optional, Union\n",
    "from collections import namedtuple\n",
    "import torch\n",
    "import math\n",
    "import os"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2",
   "metadata": {},
   "source": [
    "Below are some additional functions that we wish to use in our genetic programming example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3",
   "metadata": {},
   "outputs": [],
   "source": [
    "class AdditionalTorchFunctions:\n",
    "    @staticmethod\n",
    "    def _forbid_zero(x: torch.Tensor) -> torch.Tensor:\n",
    "        \"\"\"\n",
    "        Move x away from 0 if its absolute value is less then 1e-4.\n",
    "        \"\"\"\n",
    "        tolerance = 1e-4\n",
    "        close_to_zero_from_pos = (x >= 0) & (x < tolerance)\n",
    "        close_to_zero_from_neg = (x < 0) & (x > -tolerance)\n",
    "        result = x.clone()\n",
    "        result[close_to_zero_from_pos] = tolerance\n",
    "        result[close_to_zero_from_neg] = -tolerance\n",
    "        return result\n",
    "    \n",
    "    @classmethod\n",
    "    def unary_div(cls, x: torch.Tensor) -> torch.Tensor:\n",
    "        \"\"\"\n",
    "        Unary division with protection against division-by-zero.\n",
    "        If x is not near zero, the result will be 1/x.\n",
    "        If x is near zero, then it will first be moved away from zero.\n",
    "        \"\"\"\n",
    "        return 1 / cls._forbid_zero(x)\n",
    "\n",
    "    @classmethod\n",
    "    def binary_div(cls, a: torch.Tensor, b: torch.Tensor) -> torch.Tensor:\n",
    "        \"\"\"\n",
    "        Binary division with protection against division-by-zero.\n",
    "        If b is not near zero, the result will be a/b.\n",
    "        If b is near zero, then it will first be moved away from zero.\n",
    "        \"\"\"\n",
    "        return a / cls._forbid_zero(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4",
   "metadata": {},
   "source": [
    "Now, we present the definition of an `Instruction`. An `Instruction` is a callable object which has access to a read-only input memory and to a runtime stack. Depending on how it was initialized, an `Instruction` can pull its arguments from the runtime stack or from the input memory. After processing its arguments, the `Instruction` will push its result onto the runtime stack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5",
   "metadata": {},
   "outputs": [],
   "source": [
    "_PopResult = namedtuple(\"_PopResult\", [\"tensor_a\", \"pop_mask\"])\n",
    "_PopPairResult = namedtuple(\"_PopPairResult\", [\"tensor_a\", \"tensor_b\", \"pop_mask\"])\n",
    "\n",
    "\n",
    "class Instruction:\n",
    "    def __init__(\n",
    "        self,\n",
    "        *,\n",
    "        inputs: torch.Tensor,\n",
    "        stack: CList,\n",
    "        arity: int,\n",
    "        function: Optional[Callable] = None,\n",
    "        input_slot: Optional[int] = None,\n",
    "        operation: Optional[str] = None,\n",
    "    ):\n",
    "        [batch_size] = stack.batch_shape\n",
    "        inputs_batch_size, input_size = inputs.shape\n",
    "        assert inputs_batch_size == batch_size\n",
    "\n",
    "        self.input_size = input_size\n",
    "        self.stack = stack\n",
    "        self.inputs = inputs\n",
    "        self.arity = int(arity)\n",
    "\n",
    "        self.function = None\n",
    "        self.input_slot = None\n",
    "        self.operation = None\n",
    "        \n",
    "        instr_definitions = 0\n",
    "\n",
    "        if function is not None:\n",
    "            self.function = function\n",
    "            instr_definitions += 1\n",
    "\n",
    "        if input_slot is not None:\n",
    "            assert self.arity == 0\n",
    "            self.input_slot = input_slot\n",
    "            instr_definitions += 1\n",
    "\n",
    "        if operation is not None:\n",
    "            assert self.arity == 0\n",
    "            assert operation in (\"pass\", \"swap\", \"duplicate\")\n",
    "            self.operation = operation\n",
    "            instr_definitions += 1\n",
    "\n",
    "        assert instr_definitions == 1, \"Please specify only one of these: `function`, `input_slot`, or `operation`.\"        \n",
    "        assert self.arity in (0, 1, 2)\n",
    "\n",
    "    def _pop(self, where: torch.Tensor) -> _PopResult:\n",
    "        suitable = self.stack.length >= 1\n",
    "        where = where & suitable\n",
    "        return _PopResult(tensor_a=self.stack.pop_(where=where), pop_mask=where)\n",
    "\n",
    "    def _pop_pair(self, where: torch.Tensor) -> _PopPairResult:\n",
    "        suitable = self.stack.length >= 2\n",
    "        where = where & suitable\n",
    "        b = self.stack.pop_(where=where)\n",
    "        a = self.stack.pop_(where=where)\n",
    "        return _PopPairResult(tensor_a=a, tensor_b=b, pop_mask=where)\n",
    "    \n",
    "    def _push(self, x: torch.Tensor, where: torch.Tensor):\n",
    "        self.stack.push_(x, where=where)\n",
    "    \n",
    "    def _push_input(self, input_slot: int, where: torch.Tensor):\n",
    "        input_values = self.inputs[:, input_slot]\n",
    "        self.stack.push_(input_values, where=where)\n",
    "\n",
    "    def __call__(self, where: torch.Tensor):\n",
    "        if self.function is not None:\n",
    "            fn = self.function\n",
    "            arity = self.arity\n",
    "\n",
    "            if arity == 0:\n",
    "                self._push(fn(), where=where)\n",
    "            elif arity == 1:\n",
    "                a, where = self._pop(where=where)\n",
    "                self._push(fn(a), where=where)\n",
    "            elif arity == 2:\n",
    "                a, b, where = self._pop_pair(where=where)\n",
    "                self._push(fn(a, b), where=where)\n",
    "            else:\n",
    "                assert False\n",
    "\n",
    "        if self.input_slot is not None:\n",
    "            self._push_input(self.input_slot, where=where)\n",
    "        \n",
    "        if self.operation is not None:\n",
    "            if self.operation == \"pass\":\n",
    "                pass\n",
    "            elif self.operation == \"swap\":\n",
    "                a, b, where = self._pop_pair(where=where)\n",
    "                self._push(b, where=where)\n",
    "                self._push(a, where=where)\n",
    "            elif self.operation == \"duplicate\":\n",
    "                a, where = self._pop(where=where)\n",
    "                self._push(a, where=where)\n",
    "                self._push(a, where=where)\n",
    "            else:\n",
    "                assert False, f\"unknown operation: {operation}\"\n",
    "    \n",
    "    def __repr__(self) -> str:\n",
    "        result = []\n",
    "        \n",
    "        def puts(*xs: str):\n",
    "            for x in xs:\n",
    "                result.append(str(x))\n",
    "\n",
    "        puts(type(self).__name__, \"(\")\n",
    "\n",
    "        if self.function is not None:\n",
    "            if hasattr(self.function, \"__name__\"):\n",
    "                fn_name = self.function.__name__\n",
    "            else:\n",
    "                fn_name = repr(self.function)\n",
    "            puts(\"function=\", fn_name)\n",
    "\n",
    "        if self.input_slot is not None:\n",
    "            puts(\"input_slot=\", self.input_slot)\n",
    "\n",
    "        if self.operation is not None:\n",
    "            puts(\"operation=\", repr(self.operation))\n",
    "            \n",
    "        puts(\", arity=\", self.arity)\n",
    "        puts(\")\")\n",
    "        return \"\".join(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6",
   "metadata": {},
   "source": [
    "Now we define a stack-based `Interpreter`.\n",
    "This `Interpreter` supports batching, and can work in a vectorized manner. According to the batching scheme of this `Interpreter`, each program in the batch has its own input, and produces its own output."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Interpreter:\n",
    "    def __init__(\n",
    "        self,\n",
    "        *,\n",
    "        max_stack_length: int,\n",
    "        batch_size: int,\n",
    "        input_size: int,\n",
    "        unary_ops: Iterable,\n",
    "        binary_ops: Iterable,\n",
    "        pass_means_terminate: bool = True,\n",
    "        device: Optional[Union[str, torch.device]] = None,\n",
    "    ):\n",
    "        if device is None:\n",
    "            device = torch.device(\"cpu\")\n",
    "        else:\n",
    "            device = torch.device(device)\n",
    "            \n",
    "        self._batch_size = int(batch_size)\n",
    "        self._input_size = int(input_size)\n",
    "        self._max_stack_length = int(max_stack_length)\n",
    "\n",
    "        self._stack = CList(\n",
    "            max_length=self._max_stack_length,\n",
    "            batch_size=self._batch_size,\n",
    "            dtype=torch.float32,\n",
    "            device=device,\n",
    "            verify=False,\n",
    "        )\n",
    "        self._inputs = torch.zeros(self._batch_size, self._input_size, dtype=torch.float32, device=device)\n",
    "\n",
    "        self._instructions = []\n",
    "        self._pass_means_terminate = bool(pass_means_terminate)\n",
    "        \n",
    "        for operation in (\"pass\", \"swap\", \"duplicate\"):\n",
    "            self._instructions.append(\n",
    "                Instruction(\n",
    "                    inputs=self._inputs,\n",
    "                    stack=self._stack,\n",
    "                    arity=0,\n",
    "                    operation=operation,\n",
    "                )\n",
    "            )\n",
    "\n",
    "        for i_input in range(self._input_size):\n",
    "            self._instructions.append(\n",
    "                Instruction(\n",
    "                    inputs=self._inputs,\n",
    "                    stack=self._stack,\n",
    "                    arity=0,\n",
    "                    input_slot=i_input,\n",
    "                )\n",
    "            )\n",
    "\n",
    "        for unary_op in unary_ops:\n",
    "            self._instructions.append(\n",
    "                Instruction(\n",
    "                    inputs=self._inputs,\n",
    "                    stack=self._stack,\n",
    "                    arity=1,\n",
    "                    function=unary_op,\n",
    "                )\n",
    "            )\n",
    "\n",
    "        for binary_op in binary_ops:\n",
    "            self._instructions.append(\n",
    "                Instruction(\n",
    "                    inputs=self._inputs,\n",
    "                    stack=self._stack,\n",
    "                    arity=2,\n",
    "                    function=binary_op,\n",
    "                )\n",
    "            )\n",
    "\n",
    "    @property\n",
    "    def instructions(self) -> list:\n",
    "        return self._instructions\n",
    "    \n",
    "    @property\n",
    "    def stack(self) -> CList:\n",
    "        return self._stack\n",
    "\n",
    "    def run(self, program_batch: torch.Tensor, input_batch: torch.Tensor) -> torch.Tensor:\n",
    "        self._stack.clear()\n",
    "        program_batch = torch.as_tensor(program_batch, dtype=torch.int64, device=self._stack.device)\n",
    "        batch_size, program_length = program_batch.shape\n",
    "        assert batch_size == self._batch_size\n",
    "\n",
    "        if self._pass_means_terminate:\n",
    "            program_running = torch.ones(batch_size, dtype=torch.bool, device=self._stack.device)\n",
    "        else:\n",
    "            program_running = None\n",
    "\n",
    "        self._inputs[:] = input_batch\n",
    "\n",
    "        for t in range(program_length):\n",
    "            instruction_codes = program_batch[:, t]\n",
    "\n",
    "            if self._pass_means_terminate:\n",
    "                program_running = program_running & (instruction_codes != 0)\n",
    "\n",
    "            for i_instruction in range(1, len(self._instructions)):\n",
    "                instruction_codes_match = (instruction_codes == i_instruction)\n",
    "                if self._pass_means_terminate:\n",
    "                    instruction_codes_match = instruction_codes_match & program_running\n",
    "\n",
    "                self._instructions[i_instruction](where=instruction_codes_match)\n",
    "\n",
    "        return self._stack.get(-1, default=0.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8",
   "metadata": {},
   "source": [
    "Above, we have defined a batched interpreter where each program works on its own input and produces its own output. However, when doing symbolic regression, the most common scheme is to have fixed batch of inputs that is to be used by each program within the program batch. To be compatible with this scheme, we now define an `InterpreterWithInputBatch`, which, upon receiving a batch of inputs and a separate batch of programs, arranges them in this manner:\n",
    "\n",
    "```\n",
    "input0 -> program0 -> output0,0\n",
    "input1 -> program0 -> output1,0\n",
    "input2 -> program0 -> output2,0\n",
    "  :         :           :\n",
    "inputN -> program0 -> outputN,0\n",
    "input0 -> program1 -> output0,1\n",
    "input1 -> program1 -> output1,1\n",
    "input2 -> program1 -> output2,1\n",
    "  :         :           :\n",
    "inputN -> program1 -> outputN,1\n",
    "  :         :           :\n",
    "  :         :           :\n",
    "input0 -> programM -> output0,M\n",
    "input1 -> programM -> output1,M\n",
    "input2 -> programM -> output2,M\n",
    "  :         :           :\n",
    "inputN -> programM -> outputN,M\n",
    "```\n",
    "\n",
    "After creating this flattened batch, `InterpreterWithInputBatch` passes it to its own internal `Interpreter`.\n",
    "`InterpreterWithInputBatch` also defines a method for computing the mean squared error which compares the programs' outputs against the desired outputs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9",
   "metadata": {},
   "outputs": [],
   "source": [
    "class InterpreterWithInputBatch:\n",
    "    def __init__(\n",
    "        self,\n",
    "        *,\n",
    "        max_stack_length: int,\n",
    "        program_batch_size: int,\n",
    "        input_size: int,\n",
    "        input_batch_size: int,\n",
    "        unary_ops: Iterable,\n",
    "        binary_ops: Iterable,\n",
    "        pass_means_terminate: bool = True,\n",
    "        device: Optional[Union[str, torch.device]] = None,\n",
    "    ):\n",
    "        self._program_batch_size = int(program_batch_size)\n",
    "        self._input_batch_size = int(input_batch_size)\n",
    "        self._input_size = int(input_size)\n",
    "        self._batch_size = self._program_batch_size * self._input_batch_size\n",
    "        \n",
    "        self._interpreter = Interpreter(\n",
    "            max_stack_length=max_stack_length,\n",
    "            batch_size=self._batch_size,\n",
    "            input_size=self._input_size,\n",
    "            unary_ops=unary_ops,\n",
    "            binary_ops=binary_ops,\n",
    "            pass_means_terminate=pass_means_terminate,\n",
    "            device=device,\n",
    "        )\n",
    "\n",
    "    def run(self, program_batch: torch.Tensor, input_batch: torch.Tensor) -> torch.Tensor:\n",
    "        programs = torch.repeat_interleave(program_batch, self._input_batch_size, dim=0)\n",
    "        inputs = (\n",
    "            input_batch\n",
    "            .expand(self._program_batch_size, self._input_batch_size, self._input_size)\n",
    "            .reshape(self._batch_size, self._input_size)\n",
    "        )\n",
    "        return (\n",
    "            self._interpreter\n",
    "            .run(programs, inputs)\n",
    "            .reshape(self._program_batch_size, self._input_batch_size)\n",
    "        )\n",
    "\n",
    "    def compute_mean_squared_error(\n",
    "        self,\n",
    "        program_batch: torch.Tensor,\n",
    "        input_batch: torch.Tensor,\n",
    "        desired_output_batch: torch.Tensor\n",
    "    ) -> torch.Tensor:\n",
    "        output = self.run(program_batch, input_batch)\n",
    "        return torch.mean((output - desired_output_batch) ** 2, dim=-1)\n",
    "    \n",
    "    @property\n",
    "    def stack(self) -> CList:\n",
    "        return self._interpreter.stack\n",
    "\n",
    "    @property\n",
    "    def instructions(self) -> list:\n",
    "        return self._interpreter.instructions\n",
    "    \n",
    "    @property\n",
    "    def program_batch_size(self) -> int:\n",
    "        return self._program_batch_size"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10",
   "metadata": {},
   "source": [
    "Now that we have our `InterpreterWithInputBatch`, we can define a `Problem` class where the goal is to minimize this mean squared error."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "11",
   "metadata": {},
   "outputs": [],
   "source": [
    "class ProgramSynthesisProblem(Problem):\n",
    "    def __init__(\n",
    "        self,\n",
    "        unary_ops: Iterable,\n",
    "        binary_ops: Iterable,\n",
    "        inputs: Iterable,\n",
    "        outputs: Iterable,\n",
    "        program_length: int,\n",
    "        pass_means_terminate: bool = True,\n",
    "        device: Optional[Union[str, torch.device]] = None,\n",
    "        num_actors: Optional[Union[str, int]] = None,\n",
    "    ):\n",
    "        if device is None:\n",
    "            device = torch.device(\"cpu\")\n",
    "        else:\n",
    "            device = torch.device(device)\n",
    "\n",
    "        self._program_length = int(program_length)\n",
    "        self._inputs = torch.as_tensor(inputs, dtype=torch.float32, device=device)\n",
    "        self._outputs = torch.as_tensor(outputs, dtype=torch.float32, device=device)\n",
    "        \n",
    "        self._input_batch_size, self._input_size = self._inputs.shape\n",
    "        [output_batch_size] = self._outputs.shape\n",
    "        assert output_batch_size == self._input_batch_size\n",
    "\n",
    "        self._unary_ops = list(unary_ops)\n",
    "        self._binary_ops = list(binary_ops)\n",
    "        self._pass_means_terminate = pass_means_terminate\n",
    "\n",
    "        self._interpreter: Optional[InterpreterWithInputBatch] = None\n",
    "        num_instructions = len(self._get_interpreter(1).instructions)\n",
    "\n",
    "        super().__init__(\n",
    "            objective_sense=\"min\",\n",
    "            solution_length=self._program_length,\n",
    "            dtype=torch.int64,\n",
    "            bounds=(0, num_instructions - 1),\n",
    "            device=device,\n",
    "            #num_actors=num_actors,\n",
    "            store_solution_stats=True,\n",
    "        )\n",
    "    \n",
    "    def _get_interpreter(self, num_programs: int) -> InterpreterWithInputBatch:\n",
    "        if (self._interpreter is None) or (num_programs > self._interpreter.program_batch_size):\n",
    "            self._interpreter = InterpreterWithInputBatch(\n",
    "                max_stack_length=self._program_length,\n",
    "                program_batch_size=num_programs,\n",
    "                input_size=self._input_size,\n",
    "                input_batch_size=self._input_batch_size,\n",
    "                unary_ops=self._unary_ops,\n",
    "                binary_ops=self._binary_ops,\n",
    "                pass_means_terminate=self._pass_means_terminate,\n",
    "                device=self._inputs.device,\n",
    "            )\n",
    "        return self._interpreter\n",
    "    \n",
    "    def _evaluate_batch(self, batch: SolutionBatch):\n",
    "        num_programs = len(batch)\n",
    "        interpreter = self._get_interpreter(num_programs)\n",
    "        \n",
    "        if num_programs < interpreter.program_batch_size:\n",
    "            programs = torch.zeros(\n",
    "                (interpreter.program_batch_size, self.solution_length),\n",
    "                dtype=torch.int64,\n",
    "                device=interpreter.stack.device\n",
    "            )\n",
    "            programs[:num_programs, :] = batch.values\n",
    "        else:\n",
    "            programs = batch.values\n",
    "        \n",
    "        batch.set_evals(interpreter.compute_mean_squared_error(programs, self._inputs, self._outputs)[:num_programs])\n",
    "    \n",
    "    @property\n",
    "    def instructions(self) -> list:\n",
    "        interpreter = self._get_interpreter(1)\n",
    "        return interpreter.instructions\n",
    "    \n",
    "    @property\n",
    "    def instruction_dict(self) -> dict:\n",
    "        result = {}\n",
    "        for i_instruction, instruction in enumerate(self.instructions):\n",
    "            result[i_instruction] = instruction\n",
    "        return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12",
   "metadata": {},
   "source": [
    "We now define a target function (the function whose definition will be searched for by our evolutionary algorithm). In the case of our example, we are searching for this function:\n",
    "\n",
    "$$\n",
    "\\frac{x + y}{cos(x)} + sin(y)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "13",
   "metadata": {},
   "outputs": [],
   "source": [
    "def target_function(inputs: torch.Tensor) -> torch.Tensor:\n",
    "    x = inputs[:, 0]\n",
    "    y = inputs[:, 1]\n",
    "    return AdditionalTorchFunctions.binary_div(x + y, torch.cos(x)) + torch.sin(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14",
   "metadata": {},
   "source": [
    "Below, we produce a deterministic input set, and then, using the target function, we obtain our target outputs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "15",
   "metadata": {},
   "outputs": [],
   "source": [
    "inputs = []\n",
    "input_values = [-5, -3, -1, 1, 3, 5]\n",
    "for x in input_values:\n",
    "    for y in input_values:\n",
    "        inputs.append([x, y])\n",
    "inputs = torch.as_tensor(inputs, dtype=torch.float32)\n",
    "outputs = target_function(inputs)\n",
    "\n",
    "inputs, outputs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "16",
   "metadata": {},
   "outputs": [],
   "source": [
    "inputs.shape, outputs.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "17",
   "metadata": {},
   "outputs": [],
   "source": [
    "device = \"cpu\"  # change this to e.g. \"cuda:0\" for exploiting the GPU\n",
    "\n",
    "problem = ProgramSynthesisProblem(\n",
    "    inputs=inputs,\n",
    "    outputs=outputs,\n",
    "    unary_ops=[torch.neg, torch.sin, torch.cos, AdditionalTorchFunctions.unary_div],\n",
    "    binary_ops=[torch.add, torch.sub, torch.mul, AdditionalTorchFunctions.binary_div],\n",
    "    program_length=20,\n",
    "    device=device,\n",
    ")\n",
    "\n",
    "problem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18",
   "metadata": {},
   "source": [
    "Below is a simple mutation function which changes each symbol with a probability of 10%"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "19",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mutate_programs(programs: torch.Tensor) -> torch.Tensor:\n",
    "    num_instructions = len(problem.instructions)\n",
    "    mutate = torch.rand(programs.shape, device=programs.device) < 0.1\n",
    "    num_mutations = int(torch.count_nonzero(mutate))\n",
    "    result = programs.clone()\n",
    "    mutated = torch.randint(0, num_instructions, (num_mutations,), device=programs.device)\n",
    "    result[mutate] = mutated\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20",
   "metadata": {},
   "source": [
    "Now we instantiate our genetic algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "21",
   "metadata": {},
   "outputs": [],
   "source": [
    "ga = GeneticAlgorithm(\n",
    "    problem,\n",
    "    operators=[TwoPointCrossOver(problem, tournament_size=4), mutate_programs],\n",
    "    re_evaluate=False,\n",
    "    popsize=5000,\n",
    ")\n",
    "ga"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "22",
   "metadata": {},
   "outputs": [],
   "source": [
    "StdOutLogger(ga)\n",
    "ga.run(50)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23",
   "metadata": {},
   "source": [
    "Below is the best solution encountered so far, hopefully with its evaluation result expressing a near-zero error value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "24",
   "metadata": {},
   "outputs": [],
   "source": [
    "best_solution = ga.status[\"best\"]\n",
    "best_solution"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25",
   "metadata": {},
   "source": [
    "The program reported above can be analyzed with the help of this instruction set:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "26",
   "metadata": {},
   "outputs": [],
   "source": [
    "problem.instruction_dict"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
